package algorithm.niuke;

public class L有序矩阵中第K小的元素 {
    /*
     * 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。
     * 
     * 示例:
     * 
     * matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,
     * 
     * 返回 13。
     */
    public int kthSmallest(int[][] matrix, int k) {
        /*
         * i,j rank must greater or equal (i+1) * (j+1)
         */
        int row = matrix.length;
        int col = matrix[0].length;
        int[] min1 = { 0, 0 };
        int[] min2 = { 0, 0 };
        int len = 1;
        while (len < k) {
            
        }
        return matrix[min1[0]][min1[1]];
    }

    int row = 0;
    int col = 0;

    int rank(int[][] mat, int i, int j) {
        int rank = (i + 1) * (j + 1);
        int num = mat[i][j];
        for (int r = 0; r < i; i++) {
            for (int c = j + 1; c < col; c++) {
                if (num >= mat[r][c]) {
                    rank++;
                } else {
                    break;
                }
            }
        }
        for (int c = 0; c < j; c++) {
            for (int r = i + 1; r < row; r++) {
                if (num >= mat[r][c]) {
                    rank++;
                } else {
                    break;
                }
            }
        }
        return rank;
    }
}
